package cc.owoo.godpen.structure;

import java.util.AbstractCollection;
import java.util.Iterator;

/**
 * 可由调用者自行控制节点的链表（非线程安全的）
 * Created by nimensei
 * 2022-05-04 上午 09:49
 **/
public class CustomLinkedList<T> implements Iterable<CustomLinkedList.Node<T>> {
    private Node<T> first;// 头节点
    private Node<T> last;// 尾节点
    private int size = 0;// 链表长度

    /**
     * 获取头元素
     *
     * @return 头部元素
     */
    public T getFirst() {
        return first == null ? null : first.value;
    }

    /**
     * 获取尾部元素
     *
     * @return 尾部元素
     */
    public T getLast() {
        return last == null ? null : last.value;
    }

    /**
     * 判断节点是否为链表的头节点
     *
     * @param node 需要判断的节点
     * @return 是否为头节点
     */
    public boolean isFirst(Node<T> node) {
        return first == node;
    }

    /**
     * 判断节点是否为链表的尾节点
     *
     * @param node 需要判断的节点
     * @return 是否为尾节点
     */
    public boolean isLast(Node<T> node) {
        return last == node;
    }

    /**
     * 获取头部节点
     *
     * @return 头部节点对象
     */
    public Node<T> getFirstNode() {
        return first;
    }

    /**
     * 获取尾部节点
     *
     * @return 尾部节点对象
     */
    public Node<T> getLastNode() {
        return last;
    }

    /**
     * 获取指定下标的元素
     *
     * @param index 元素下标
     * @return 元素
     */
    public T get(int index) {
        return getNode(index).value;
    }

    /**
     * 获取指定下标的节点
     *
     * @param index 节点下标
     * @return 节点对象
     */
    public Node<T> getNode(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("下标越界：size = " + size + ", index = " + index);
        if (index < size >> 1) {
            Node<T> node = first;
            while (--index >= 0)
                node = node.next;
            return node;
        } else {
            index = size - index - 1;
            Node<T> node = last;
            while (--index >= 0)
                node = node.prev;
            return node;
        }
    }


    /**
     * 删除并返回头部元素
     *
     * @return 头部元素
     */
    public T removeFirst() {
        var node = removeFirstNode();
        return node == null ? null : node.value;
    }

    /**
     * 删除并返回头部节点
     *
     * @return 头部节点
     */
    public Node<T> removeFirstNode() {
        if (first == null)
            return null;
        var node = first;
        node.linked = null;
        if (size == 1)
            first = last = null;
        else {
            var next = first.next;
            next.prev = null;
            first.next = null;
            first = next;
        }
        --size;
        return node;
    }

    /**
     * 删除并返回尾部元素
     *
     * @return 尾部元素
     */
    public T removeLast() {
        var node = removeLastNode();
        return node == null ? null : node.value;
    }

    /**
     * 删除并返回尾部节点
     *
     * @return 尾部节点
     */
    public Node<T> removeLastNode() {
        if (last == null)
            return null;
        var node = last;
        node.linked = null;
        if (size == 1)
            first = last = null;
        else {
            var prev = last.prev;
            prev.next = null;
            last.prev = null;
            last = prev;
        }
        --size;
        return node;
    }

    /**
     * 从头部添加一个元素
     *
     * @param item 元素
     */
    public Node<T> addFirst(T item) {
        var node = new Node<>(item);
        addFirst(node);
        return node;
    }

    /**
     * 向头部添加一个节点
     *
     * @param node 节点
     */
    public void addFirst(Node<T> node) {
        if (node == null)
            throw new IllegalArgumentException("节点不能为空");
        node.linked = this;
        if (first == null)
            first = last = node;
        else {
            node.next = first;
            first = last.prev = node;
        }
        ++size;
    }

    /**
     * 从尾部添加一个元素
     *
     * @param item 元素
     */
    public Node<T> addLast(T item) {
        var node = new Node<>(item);
        addLast(node);
        return node;
    }

    /**
     * 从尾部添加一个节点
     *
     * @param node 节点
     */
    public void addLast(Node<T> node) {
        if (node == null)
            throw new IllegalArgumentException("节点不能为空");
        node.linked = this;
        if (first == null)
            first = last = node;
        else {
            node.prev = last;
            last = last.next = node;
        }
        ++size;
    }

    /**
     * 删除元素
     *
     * @param item 需要删除的元素
     */
    public void remove(T item) {
        var now = first;
        while (now != null) {
            var next = now.next;
            if (now.value == item)
                remove(now);
            now = next;
        }
    }

    /**
     * 删除节点
     *
     * @param node 需要删除的节点
     */
    public void remove(Node<T> node) {
        checkNode(node);
        if (node == first) {
            if (size == 1)
                first = last = null;
            else {
                first = first.next;
                first.prev = null;
            }
        } else if (node == last) {
            if (size == 1)
                first = last = null;
            else {
                last = last.prev;
                last.next = null;
            }
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = node.next = null;
        }
        node.linked = null;
        --size;
    }

    /**
     * 删除指定下标的元素
     *
     * @param index 需要删除的下标
     * @return 被删除的节点
     */
    public T remove(int index) {
        return removeNode(index).value;
    }

    /**
     * 删除指定下标的节点
     *
     * @param index 需要删除的下标
     * @return 被删除的节点
     */
    public Node<T> removeNode(int index) {
        var node = getNode(index);
        remove(node);
        return node;
    }

    /**
     * 删除节点以及节点前面的所有节点
     *
     * @param node 需要删除的节点
     * @return 删除数量
     */
    public int removeToFirst(Node<T> node) {
        checkNode(node);
        first = node.next;
        if (first == null)
            last = null;
        else
            first.prev = null;
        int count = 0;
        while (node != null) {
            Node<T> prev = node.prev;
            node.prev = null;
            node.next = null;
            node = prev;
            ++count;
        }
        size -= count;
        return count;
    }

    /**
     * 删除节点以及节点后面的所有节点
     *
     * @param node 需要删除的节点
     * @return 删除数量
     */
    public int removeToLast(Node<T> node) {
        checkNode(node);
        last = node.prev;
        if (last == null)
            first = null;
        else
            last.next = null;
        int count = 0;
        while (node != null) {
            Node<T> next = node.next;
            node.prev = null;
            node.next = null;
            node = next;
            ++count;
        }
        size -= count;
        return count;
    }

    /**
     * 删除下标以及下标前面的所有节点
     *
     * @param index 需要删除的节点下标
     * @return 删除数量
     */
    public int removeToFirst(int index) {
        return removeToFirst(getNode(index));
    }

    /**
     * 删除下标以及下标后面的所有节点
     *
     * @param index 需要删除的节点下标
     * @return 删除数量
     */
    public int removeToLast(int index) {
        return removeToLast(getNode(index));
    }

    /**
     * 在当前节点与当前的上一个节点之间插入一个新元素，并返回常见的新节点
     *
     * @param node 当前节点
     * @param item 需要插入的元素
     * @return 插入元素后生成的节点
     */
    public Node<T> insertFirst(Node<T> node, T item) {
        if (node == null)
            throw new NullPointerException("节点不能为空");
        if (node.linked != this)
            throw new IllegalArgumentException("该节点属于其他链表：" + node);
        Node<T> create = new Node<>(this, item);
        create.next = node;
        if (node == first)
            first = node.prev = create;
        else {
            create.prev = node.prev;
            create.prev.next = create;
            node.prev = create;
        }
        return create;
    }

    /**
     * 在当前节点与当前的下一个节点之间插入一个新元素，并返回常见的新节点
     *
     * @param node 当前节点
     * @param item 需要插入的元素
     * @return 插入元素后生成的节点
     */
    public Node<T> insertLast(Node<T> node, T item) {
        if (node == null)
            throw new NullPointerException("节点不能为空");
        if (node.linked != this)
            throw new IllegalArgumentException("该节点属于其他链表：" + node);
        Node<T> create = new Node<>(this, item);
        create.prev = node;
        if (node == last)
            last = node.next = create;
        else {
            create.next = node.next;
            create.next.prev = create;
            node.next = create;
        }
        return create;
    }

    /**
     * 将链表的元素倒叙排列，并生成新的链表
     *
     * @return 倒叙排序后的新链表
     */
    public CustomLinkedList<T> reverse() {
        CustomLinkedList<T> list = new CustomLinkedList<>();
        Node<T> now = first;
        while (now != null) {
            Node<T> node = new Node<>(list, now.value);
            if (list.first == null)
                list.first = list.last = node;
            else {
                node.next = list.first;
                list.first = list.first.prev = node;
            }
            now = now.next;
        }
        list.size = size;
        return list;
    }

    /**
     * 将集合的元素添加到链表
     *
     * @param collection 集合
     */
    public void addAll(AbstractCollection<T> collection) {
        if (collection == null)
            throw new NullPointerException("集合不能为空");
        for (var item : collection)
            addLast(item);
    }

    /**
     * 将另一个链表的所有元素添加到尾部
     *
     * @param customLinkedList 需要添加的链表
     */
    public void addAll(CustomLinkedList<T> customLinkedList) {
        if (customLinkedList == null)
            throw new NullPointerException("链表不能为空");
        Node<T> node = customLinkedList.first;
        Node<T> last = this.last;
        while (node != null) {
            Node<T> now = new Node<>(node.value);
            if (last == null)
                this.first = this.last = last = now;
            else {
                now.prev = last;
                last = last.next = now;
            }
            node = node.next;
        }
    }

    /**
     * 当前链表长度
     *
     * @return 长度
     */
    public int size() {
        return size;
    }

    /**
     * 检查节点是否可以被操作
     *
     * @param node 需要检查的节点对象
     */
    private void checkNode(Node<T> node) {
        if (node == null)
            throw new IllegalArgumentException("节点不能为空");
        if (node.linked != this)
            throw new IllegalArgumentException("该节点属于其他链表：" + node);
    }

    @Override
    public Iterator<Node<T>> iterator() {
        return new Iterator<>() {
            Node<T> node = first;

            @Override
            public boolean hasNext() {
                return node != null;
            }

            @Override
            public Node<T> next() {
                Node<T> temp = node;
                node = node.next;
                return temp;
            }
        };
    }

    /**
     * 清空链表，执行这个函数会将所有节点的链接断开，以便垃圾回收器回收
     */
    public void clear() {
        Node<T> node = first;
        while (node != null) {
            Node<T> temp = node;
            node = node.next;
            temp.prev = temp.next = null;
        }
        first = last = null;
        size = 0;
    }

    /**
     * 节点
     *
     * @param <T> 元素类型
     */
    public static class Node<T> {
        private CustomLinkedList<T> linked;// 所在链表
        private Node<T> prev;// 上一个节点
        private Node<T> next;// 下一个节点
        private T value;// 节点元素

        public Node() {
        }

        public Node(T item) {
            this.value = item;
        }

        private Node(CustomLinkedList<T> linked, T item) {
            this.linked = linked;
            this.value = item;
        }

        /**
         * 删除该节点以及该节点前面的所有节点
         *
         * @return 删除数量
         */
        public int removeToFirst() {
            checkLinked();
            return linked.removeToFirst(this);
        }

        /**
         * 删除该节点以及该节点后面的所有节点
         *
         * @return 删除数量
         */
        public int removeToLast() {
            checkLinked();
            return linked.removeToLast(this);
        }

        /**
         * 判断该节点是否存在任何一个链表中
         *
         * @return 是否存在任何一个链表中
         */
        public boolean isExist() {
            return linked != null;
        }

        /**
         * 获取上一个节点
         *
         * @return 上一个节点
         */
        public Node<T> prev() {
            return prev;
        }

        /**
         * 获取下一个节点
         *
         * @return 下一个节点
         */
        public Node<T> next() {
            return next;
        }

        /**
         * 获取该节点的元素
         *
         * @return 元素
         */
        public T value() {
            return value;
        }

        /**
         * 删除当前节点
         */
        public void remove() {
            checkLinked();
            linked.remove(this);
        }

        /**
         * 在当前节点与当前的上一个节点之间插入一个新元素，并返回创建的新节点
         */
        public Node<T> insertFirst(T value) {
            return linked.insertFirst(this, value);
        }

        /**
         * 在当前节点与当前的下一个节点之间插入一个新元素，并返回创建的新节点
         */
        public Node<T> insertLast(T value) {
            return linked.insertLast(this, value);
        }

        private T value(Node<T> node) {
            return node == null ? null : node.value;
        }

        /**
         * 检查父链表是否为空，如果为空则抛出异常
         */
        private void checkLinked() {
            if (linked == null)
                throw new NullPointerException("该节点没有被添加到任何链表中");
        }

        @Override
        public String toString() {
            return "Node{" +
                    "prev=" + value(prev) +
                    ", value=" + value +
                    ", next=" + value(next) +
                    '}';
        }
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append('[');
        Node<T> now = first;
        while (now != null) {
            if (string.length() > 1)
                string.append(", ");
            string.append(now.value);
            now = now.next;
        }
        string.append(']');
        return string.toString();
    }
}
